#include <stdio.h> 
#include <string.h> 
#include <stdlib.h> 
#define N 73          //叶子节点数
#define  M 2*N-1      //树中节点总数
#define MAXSIZE 20000
typedef struct
{
    char data;          //节点值
    int weight;         //权重
    int parent;         //双亲节点
    int lchild;         //左孩子节点
    int rchild;         //右孩子节点
}HTNode;
typedef struct
{
    char cd[N];         //存放当前节点的哈夫曼编码
    int start;          //cd[start]~cd[n]存放哈夫曼编码
    char data;
}HCode;
HCode  hcd[N];                       //存放哈夫曼编码跟字符的结构体数组
HTNode ht[M];                        //存放哈夫曼树
char string[10000];
int fileopen(char string[])           //读入文件   
{
    FILE *fp;
    char *p = string;
    fp = fopen("D:\\file1.txt", "r");
    while (fgets(p, 1000, fp) != NULL);     //输出文章
    printf("%s", string);
    printf("\n");
    fclose(fp);
    return 0;
}
void CreateHT(HTNode ht[], int n)     //构造哈夫曼树
{
    int i, k, lnode, rnode;
    double min1, min2;
    for (i = 0; i<2 * n - 1; i++)            //所有节点的相关域置初值-1
        ht[i].parent = ht[i].lchild = ht[i].rchild = -1;
    for (i = n; i<2 * n - 1; i++)
    {
        min1 = min2 = 32767;          //lnode和rnode为权值最小的两个节点
        lnode = rnode = -1;           //只在尚未构造二叉树的节点中找
        for (k = 0; k<i - 1; k++)
            if (ht[k].parent == -1)
            {
                if (ht[k].weight<min1)
                {
                    min2 = min1; rnode = lnode;
                    min1 = ht[k].weight; lnode = k;
                }
                else if (ht[k].weight<min2)
                {
                    min2 = ht[k].weight; rnode = k;
                }
            }
        ht[lnode].parent = i; ht[rnode].parent = i;
        ht[i].weight = ht[lnode].weight + ht[rnode].weight;
        ht[i].lchild = lnode; ht[i].rchild = rnode;    //ht[i]作为双亲节点
 
    }
}
void CreateHCode(HTNode ht[], HCode hcd[], int n)  //哈弗曼编码
{
    int i, f, c;
    HCode hc;
    for (i = 0; i<n; i++)      //根据哈夫曼树求哈弗曼编码
    {
        hc.start = n; c = i;
        f = ht[i].parent;
        while (f != -1)        //循环直到无双亲节点即到达树根节点为止
        {
            if (ht[f].lchild == c)    //当前节点是其双亲节点的左孩子节点
                hc.cd[hc.start--] = '0';
            else            //当前节点是其双亲节点的右孩子节点
                hc.cd[hc.start--] = '1';
            c = f;
            f = ht[f].parent;      //再对其双亲节点进行同样的操作
        }
        hc.start++;     //start指向哈弗曼编码的开始字符
        hc.data = ht[i].data;
        hcd[i] = hc;
    }
    printf("\n");
}
void createht(HTNode ha[])        //录入可能出现的字符
{
    int i = 0;
    char ch;
    ha[i].data = ' '; i++;        //每个字符有对应的一个i值
    ha[i].data = ','; i++;
    ha[i].data = '.'; i++;
    ha[i].data = '('; i++;
    ha[i].data = ')'; i++;
    ha[i].data = '?'; i++;
    ha[i].data = '"'; i++;
    ha[i].data = '\''; i++;
    ha[i].data = '!'; i++;
    ha[i].data = ':'; i++;
    ha[i].data = ';'; i++;
    for (ch = '0'; ch <= '9'; ch++) {
        ha[i].data = ch;
        i++;
    }
    for (ch = 'A'; ch <= 'Z'; ch++) {
        ha[i].data = ch;
        i++;
    }
    for (ch = 'a'; ch <= 'z'; ch++) {
        ha[i].data = ch;
        i++;
    }
    for (i = 0; i<N; i++)                  //每个字符权重初始值赋为0
        ha[i].weight = 0;
}
void Sumdata(HTNode ha[], (int) &n, char *string)  //统计每个字符出现的频度
{
    char *p = string;       //指针p指向文章中的字符
    int i, k = 0;
    while (*p != '\0')
    {
        for (i = 0; i<N; i++)
            if (*p == ha[i].data)    //每扫过一个字符，该字符权值加1
            {
                ha[i].weight++;
                break;
            }
        p++;            //指向下一个
    }
    printf("文章中出现的每个字符的个数如下：\n");
    for (i = 0; i<N; i++)             //当字符频度不为0时，输出该字符的频度
        if (ha[i].weight != 0)
        {
            printf("%c--%d\t", ha[i].data, ha[i].weight);
            ht[k].data = ha[i].data; k++;
        }
    n = k;
    printf("\n");
}
void DispHCode(HTNode ht[], HCode hcd[], int n)      //输出每个字符对应的哈弗曼编码     
{
    int i, k, j;
    int num = 0;
    FILE * fp; fp = fopen("DispHcode.txt", "w");                  //文件指针
    printf("  输出哈夫曼编码:\n");
    for (i = 0; i<n; i++) {            //逐个输出字符对应的哈弗曼编码
        j = 0;
        printf("\t\t%c:", ht[i].data);  //输出字符
        fprintf(fp, "\t\t%c:", ht[i].data);
        for (k = hcd[i].start; k <= n; k++) {
            printf("%c", hcd[i].cd[k]); //输出编码 
            fprintf(fp, "%c", hcd[i].cd[k]);
            j++;
        }
    }
    fclose(fp);
}
void PrintfHCode(HTNode ht[], HCode hcd[], int n)    //输出整篇文章的哈弗曼编码
{
    FILE * fp, *fp1, *fp2;
    char ch, string[MAXSIZE];
    int i, j, k;
    fp = fopen("D:\\file1.txt", "r");
    fp1 = fopen("PrintfHCode.txt", "w");
    fp2 = fopen("decode.txt", "w");
    for (i = 0; (ch = fgetc(fp)) != EOF; i++)    //一个字符一个字符读             
    {
        string[i] = ch;
        for (j = 0; j<n; j++) {
            if (string[i] == ht[j].data) {       //循环查找与输入字符相同的编号，相同的就输出这个字符的编码  
                for (k = hcd[j].start; k <= n; k++) {
                    printf("%c", hcd[j].cd[k]);
                    fprintf(fp1, "%c", hcd[j].cd[k]);//将hcd[j].cd[k]输出到fp1中
                    fprintf(fp2, "%c", hcd[j].cd[k]);
                }
                printf(" ");
                break;
            }
        }
    }
    fclose(fp);
    fclose(fp1);
    fclose(fp2);
}
void deHCode(HTNode ht[], HCode hcd[], int n)             // 将编码换成字符
{
    char code[MAXSIZE], ch;
    FILE *fp;
    fp = fopen("decode.txt", "r");              //读取文件中的编码
    int i, j, k, m, x;
    for (i = 0; (ch = fgetc(fp)) != EOF; i++) {
        code[i] = ch;
    }
    while (code[0] != '\0')
        for (i = 0; i<n; i++)
        {
            m = 0;
            for (k = hcd[i].start, j = 0; k <= n; k++, j++)     //与原生成的哈杜曼编码进行比较
            {
                if (code[j] == hcd[i].cd[k])
                    m++;
            }
            if (m == j)
            {
                printf("%c", ht[i].data);      //遇到相等时即取出对应的字符存入对应文件中
                for (x = 0; code[x - 1] != '\0'; x++)
                {
                    code[x] = code[x + j];
                }
            }
        }
    fclose(fp);
}
void main()        //主函数
{
    char string[1000];
    HTNode ha[N];
    int x, n;
    printf("\t\t\t********************************\n");
    printf("\t\t\t*****      哈夫曼编码      *****\n");
    printf("\t\t\t********************************\n");
    while (1)
    {
        printf("\n\t\t\t**【1】---------------输入文章**");
        printf("\n\t\t\t**【2】---------------统计频度**");
        printf("\n\t\t\t**【3】---------------字符编码**");
        printf("\n\t\t\t**【4】---------------文章编码**");
        printf("\n\t\t\t**【5】---------------文章译码**");
        printf("\n\t\t\t**【6】---------------退    出**\n");
        printf("      请输入选择的编号:");
        scanf("%d", &x);
        switch (x)                         //定义switch（）选择分支结构
        {
        case 1:
            printf("读出文章为：\n");
            fileopen(string);
            break;
        case 2:
            createht(ha);
            Sumdata(ha, n, string);
            break;
        case 3:
            CreateHT(ht, n);
            CreateHCode(ht, hcd, n);
            DispHCode(ht, hcd, n);
            break;
        case 4:
            CreateHT(ht, n);
            CreateHCode(ht, hcd, n);
            PrintfHCode(ht, hcd, n);
            break;
        case 5:
            CreateHT(ht, n);
            CreateHCode(ht, hcd, n);
            deHCode(ht, hcd, n);
        case 6:
            exit(0);
        default:
            printf("输入错误!\n");
        }
    }
}